/*
 * @Author: szx
 * @Date: 2021-11-25 12:26:58
 * @LastEditTime: 2022-01-15 13:01:30
 * @Description:
 * @FilePath: \leetcode\300-399\322\322.js
 */

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */

// dp[i] 为组成金额S的最少硬币数
// const coinChange = function (coins, amount) {
//     const dp = new Array(amount + 1).fill(amount + 1);
//     dp[0] = 0;
//     for (let i = 1; i <= amount; i++) {
//         for (let c of coins) {
//             if (i - c >= 0) {
//                 dp[i] = Math.min(dp[i], dp[i - c] + 1);
//             }
//         }
//     }
//     return dp[amount] > amount ? -1 : dp[amount];
// };

// var coinChange = function (coins, amount) {
//     // 备忘录
//     let preComputed = {};

//     function getNumber(amount) {
//         // BASE CASE
//         if (amount === 0) return 0;
//         if (amount < 0) return -1;
//         // 已经计算过
//         if (preComputed[amount]) return preComputed[amount];
//         // 求最小值，所以初始化为正无穷
//         let res = Number.MAX_SAFE_INTEGER;
//         for (let coin of coins) {
//             let subProblem = getNumber(amount - coin);
//             if (subProblem === -1) continue;
//             res = Math.min(res, subProblem + 1);
//         }
//         // 结果存入备忘录
//         if (res === Number.MAX_SAFE_INTEGER) {
//             preComputed[amount] = -1;
//         } else {
//             preComputed[amount] = res;
//         }
//         return preComputed[amount] ;
//     }
//     return getNumber(amount);
// };

// dp[i] 为组成金额S的最少硬币数
const coinChange = function (coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let c of coins) {
            if (i >= c) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};
console.log(coinChange([1, 2, 5], 100));
